package done.easy_401_500;

import com.study.common.TreeNode;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

/**
 * 437. Path Sum III
 * <p>
 * 给定一个二叉树，它的每个结点都存放着一个整数值。
 * 找出路径和等于给定数值的路径总数。
 * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
 * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
 * <p>
 * 示例：
 * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
 * <p>
 * 10
 * /   \
 * 5    -3
 * /  \     \
 * 3    2    11
 * /  \    \
 * 3   -2    1
 * <p>
 * 返回 3。和等于 8 的路径有:
 * <p>
 * 1.  5 ->  3
 * 2.  5 ->  2 -> 1
 * 3. -3 -> 11
 * <p>
 * 下面这种方法非常的简洁，也是利用了前序遍历，对于每个遍历到的节点进行处理，
 * 维护一个变量pre来记录之前路径之和，然后cur为pre加上当前节点值，如果cur
 * 等于sum，那么返回结果时要加1，然后对当前节点的左右子节点调用递归函数求解
 * <p>
 * 2019-03-24 4:17 PM
 **/
@Slf4j
public class PathSumIII {

    @SuppressWarnings("all")
    public int pathSum(TreeNode root, int sum) {
        // 190324 first
        // 190516 second 看了答案才做出来
        // 190517 third 看了答案，把原来的算法优化了一下
        return -1;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(10,
                new TreeNode(5,
                        new TreeNode(3,
                                3, -2),
                        new TreeNode(2,
                                null, 1)), new TreeNode(-3,
                null, 11));
        log.info("result:{}", pathSum(root, 8));
    }
}





























/*
public int pathSum(TreeNode root, int sum) {
    if (root==null)
        return 0;
    return pathSum(root.left, sum) + pathSum(root.right, sum) + dfs(root, sum);
}

public int dfs(TreeNode node, int sum) {
    if (node==null)
        return 0;

    return (node.val == sum?1:0) + dfs(node.left, sum - node.val) + dfs(node.right, sum - node.val);
}
*/
